package lhc.alg.top100;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * description: https://leetcode.cn/problems/top-k-frequent-elements/
 *  347. 前 K 个高频元素  跟215题类似
 *   堆 解法
 *   O(N log k) O( N )
 * author: hongchen.liao
 * date:  2022/8/30
 */
public class _347_Top_K_Frequent_Elements {

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> occ = new HashMap<>();
            for(int num : nums){
                occ.put(num, occ.getOrDefault(num, 0) + 1);
            }
            //int[] 的第一个元素表示值，第二个元素表示出现的次数
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
                public int compare(int[] a, int[] b){
                    return a[1] - b[1];
                }
            });

            for(Map.Entry<Integer, Integer> entry : occ.entrySet()){
                int num = entry.getKey();
                int count = entry.getValue();
                if(pq.size() == k){
                    if(pq.peek()[1] < count){
                        pq.poll();
                        pq.offer(new int[]{num, count});
                    }
                }else{
                    pq.offer(new int[]{num, count});
                }
            }
            int[] ret = new int[k];
            for(int i = 0; i < k; i++){
                ret[i] = pq.poll()[0];
            }
            return ret;
        }
    }

}
